import java.util.HashMap;
import java.util.Map;
public class Offer_07 {
/*
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder =[3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7
* */
    Map<Integer,Integer> hashMap = new HashMap<>();
    int[] preorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        for (int i = 0; i < inorder.length; i++) {
            hashMap.put(inorder[i],i);
        }
        return recur(0,0,inorder.length-1);
    }

    private TreeNode recur(int root, int left, int right) {
        if(left > right){
            return null;
        }
        TreeNode node = new TreeNode(preorder[root]);
        int i = hashMap.get(preorder[root]);
        node.left = recur(root+1,left,i-1);
        node.right = recur(root+i-left +1,i+1,right);
        return node;
    }

    public static void main(String[] args) {
     int[] prorder = {3,9,20,15,7};
     int[] inorder = {9,3,15,20,7};
     Offer_07 offer_07 = new Offer_07();
     offer_07.buildTree(prorder,inorder).preOrder();
    }
}
